In computing architectures, stacks are regions of memory where data is added or removed in a Last-In-First-Out manner. In a processor, memory stacks are usually reserved (or allocated) for certain software application tasks. For example, in most processors, each thread of execution has a reserved region of memory. When a software application executes, it may add some of its state data to the top of the stack; when the application terminates, it may remove that data from the stack. Because the data is added and removed in a last-in-first-out manner, stack allocation is very simple and typically faster than other allocation methods, such as heap allocation.
However, when a memory stack is incorrectly written in, the data stored in the stack may be corrupted. For example, a memory space in one memory stack may be written by a task other than the one the memory stack is reserved for, or the memory stack may overflow into another. The data corruption will result in random non-deterministic behavior of the embedded system. Therefore, there is a need to detect an incorrect write to memory stack and protect the memory stack from further corruptions.
A traditional method for protecting software stacks is to use a memory management unit (MMU) on a microprocessor. The minimum stack size that can be possibly allocated by an MMU is 4096 bytes. However, certain computational systems, such as embedded systems, usually have limited memory sizes. For example, the typical software stack sizes are in the 1024 bytes to 2048 bytes range in an embedded system processor. As a result, using the MMU to allocate and protect the stacks would result in a minimum stack size of 4096 bytes and thus, would waste memory. Therefore, a new method to protect software stacks in an embedded system is needed.
A method and apparatus for protecting processing elements from buffer overflow is described in U.S. Patent Publication No. 2004/0103252 to Lee et al. (“the '252 publication”). The apparatus disclosed by the '252 publication includes a memory stack for storing a return address in a first location in a stack memory. The apparatus further includes a second location separate from the stack memory for storing an address of the first location, and a third location separate from the stack memory for storing the return address itself. Upon completion of the subroutine, the address stored in the second location may be compared to the first location in the stack memory and an interrupt signal is generated if locations are not the same. Further, according to the '252 publication, the return address stored in the third location may be compared to the return address stored in the first location in the stack memory and a second interrupt signal is generated if the addresses are not the same.
Although the method and apparatus described in the '252 publication may be effective for protecting memory stacks in an embedded system, it may nevertheless be problematic. For example, the method described in the '252 publication requires storing the return address twice in both the first location and the third location, and also storing the address of the first location in the second location. That is, the method requires more memory than the memory stack to be protected. Therefore, the method described in the '252 publication may waste a large amount of memory, which is usually a limited resource in an embedded system. Furthermore, although the method described in the '252 publication may detect stack overflow and generate an interruption signal accordingly, the detection only occurs after the incorrect write is made. Because the stack overflow may have already damaged critical data stored in another memory stack at the time it is detected, the method lacks reliability in protecting the memory stack. In addition, the method described in the '252 publication may not be capable of detecting memory stack faults other than the buffer overflow.
The disclosed system and method for protecting memory stacks are directed towards overcoming one or more of the shortcomings set forth above.